SuperStrict

Rem
bbdoc: Parser
End Rem
Rem
Module Otus.Parser

ModuleInfo "Version: 0.01"
ModuleInfo "Author: Jan Varho"
ModuleInfo "License: Public domain"

ModuleInfo "History: 0.01 Alpha"
End Rem
Import BRL.LinkedList

Import Otus.Lexer


Type TParser
	
	Const RULE_START:Int	= -1
	Const RULE_SKIP:Int		= -2
	
	Field _lexer:TLexer
	
	Field _terminals:Int
	
	Field _grammar:TRule[]
	
	Field _stream:TLexerStream
	
	Field _state:TList[], _pos:Int
	
	Method AddState:Int(s:TParseState, p:Int)
		For Local ss:TParseState = EachIn _state[p]
			If ss.rule <> s.rule Continue
			If ss.dot <> s.dot Continue
			If ss.pos <> s.pos Continue
			Return False
		Next
		
		_state[p].AddLast s
		Return True
	End Method
	
	Method ParseStep:Int()
		If _stream.Eof() Return True
		
		' Predict
		For Local s:TParseState = EachIn _state[_pos]
			Local e:Int = s.GetNext()
			If e < _terminals Continue
			
			For Local r:TRule = EachIn _grammar
				If r.l = e
					Local p:TParseState = TParseState.Create(r, 0, _pos)
					_state[_pos].AddLast p
				End If
			Next
		Next
		
		' Move
		_pos :+ 1
		If _state.length = _pos
			_state = _state[.._state.length*2]
		End If
		_state[_pos] = New TList
		
		' Scan
		Local t:TToken
		Repeat
			t = _stream.ReadObject()
			For Local r:TRule = EachIn _grammar
				If r.l <> RULE_SKIP Or r.r[0] <> t.id Continue
				t = Null
				If _stream.Eof()
					_pos :- 1
					Return True
				End If
			Next
		Until t
		
		For Local s:TParseState = EachIn _state[_pos-1]
			If s.GetNext() = t.id
				_state[_pos].AddLast s.ToNext( TCstTerm.Create(t) )
			End If
		Next
		
		' Complete
		For Local s:TParseState = EachIn _state[_pos]
			Complete s
		Next
		
	End Method
	
	Method Complete(s:TParseState)
		If Not s.IsCompleted() Return
		
		Local n:TCstNode = s.Complete()
		For Local f:TParseState = EachIn _state[s.pos]
			If f.GetNext() = s.rule.l
				Local c:TParseState = f.ToNext(n)
				If AddState(c, _pos) Complete c
			End If
		Next
	End Method
	
	Method ParseStream:TCstNode(in:TStream)
		_stream = TLexerStream.Create(in, _lexer)
		_state = New TList[16]
		_state[0] = New TList
		
		For Local r:TRule = EachIn _grammar
			If r.l = RULE_START Then _state[0].AddLast TParseState.Create(r, 0, 0)
		Next
		
		Repeat
		Until ParseStep()
		
		For Local s:TParseState = EachIn _state[_pos]
			If s.rule.l = RULE_START And s.IsCompleted() Return s.Complete()
		Next
		
		Return Null
	End Method
	
	Function Create:TParser(syntax:String[], grammar:Int[][])
		Local p:TParser = New TParser
		
		p._lexer = TLexer.Create(syntax)
		p._terminals = syntax.length
		p._grammar = New TRule[grammar.length]
		
		For Local i:Int = 0 Until grammar.length
			p._grammar[i] = TRule.Create(grammar[i])
		Next
		
		Return p
	End Function
	
End Type


Type TRule
	
	Field l:Int
	
	Field r:Int[]
	
	Function Create:TRule(rule:Int[])
		Local r:TRule = New TRule
		r.l = rule[0]
		r.r = rule[1..]
		Return r
	End Function
	
End Type


Type TParseState
	
	Field rule:TRule
	
	Field dot:Int
	
	Field pos:Int
	
	Field nodes:TCstNode[]
	
	Method GetLeft:Int()
		Return rule.l
	End Method
	
	Method GetNext:Int()
		If dot = rule.r.length Then Return -1
		Return rule.r[dot]
	End Method
	
	Method IsCompleted%()
		Return dot=rule.r.length
	End Method
	
	Method Complete:TCstNode()
		Return TCstNonTerm.Create(rule.l, nodes)
	End Method
	
	Method ToNext:TParseState(o:TCstNode = Null)
		Local s:TParseState = New TParseState
		s.rule = rule
		s.nodes = nodes[..]		'Own copy
		s.nodes[dot] = o
		s.dot = dot + 1
		s.pos = pos
		Return s
	End Method
	
	Function Create:TParseState(r:TRule, d:Int, p:Int)
		Local s:TParseState = New TParseState
		s.rule = r
		s.dot = d
		s.pos = p
		s.nodes = New TCstNode[r.r.length]
		Return s
	End Function
	
End Type


Type TCstVisitor Abstract
	
	Method InNonTerm(n:TCstNonTerm) Abstract
	
	Method OutNonTerm(n:TCstNonTerm) Abstract
	
	Method InTerm(t:TToken) Abstract
	
End Type


Type TCstNode Abstract
	
	Method Visit(v:TCstVisitor) Abstract
	
End Type


Type TCstTerm Extends TCstNode
	
	Field _token:TToken
	
	Method Visit(v:TCstVisitor)
		v.InTerm(_token)
	End Method
	
	Function Create:TCstTerm(t:TToken)
		Local c:TCstTerm = New TCstTerm
		c._token = t
		Return c
	End Function
	
End Type


Type TCstNonTerm Extends TCstNode
	
	Field _type:Int
	
	Field _children:TCstNode[]
	
	Method GetType:Int()
		Return _type
	End Method
	
	Method Visit(v:TCstVisitor)
		v.InNonTerm Self
		For Local n:TCstNode = EachIn _children
			n.Visit v
		Next
		v.OutNonTerm Self
	End Method
	
	Function Create:TCstNonTerm(t:Int, c:TCstNode[])
		Local n:TCstNonTerm = New TCstNonTerm
		n._type = t
		n._children = c		'Copy isn't required
		Return n
	End Function
	
End Type

